This invention relates generally to computer systems and more particularly to the execution of computer programs on non-native computer system architectures.
As is known in the art, computer systems which generally include a central processing unit, a main memory and input/output device interconnected by a system bus are used to execute computer programs to perform some useful task. One type of computer program is an operating system which is used to interface the central processing unit to one or more application programs. The aforementioned application programs are used by a user of the computer system to perform useful tasks. The operating system includes software resources needed by the computer system to interface each of the hardware elements to the computer system as well as to interface to the application programs. The application programs can include programs such as spreadsheets, word processors, electronic mail and so forth. The application programs execute on the computer system under the control of the operating system. In addition, the operating system also includes routines or libraries which the application programs use during execution.
It is generally known that application programs are compiled for a particular computer architecture, that is, a computer instruction set as well as a particular operating system. Exemplary computer architectures include the Alpha(copyright) architecture by Digital Equipment Corporation, assignee of the present invention, the so-called X86 architecture which is based upon a family of microprocessors designed and built by the Intel Corporation, as well as others such as the PowerPC(copyright) designed and built by Motorola, IBM and Apple, the VAX(copyright) architecture by Digital Equipment Corporation and the PARISC(copyright) architecture by Hewlett-Packard.
For the aforementioned Alpha architecture, the Alpha architecture supports the Windows NT(copyright) operating system by Microsoft Corporation, the OpenVMS(copyright) operating system by Digital Equipment Corporation and the OSF/UNIX(copyright) operating system. New architectures such as the Alpha architecture are developed in order to provide significant performance improvements.
One problem which occurs with a new architecture is that often programs written for an older architecture can not directly run on the new architecture because the instruction sets of the new architecture and the old architecture are different and the programs are not directly transferrable.
Several approaches have been developed to assist users to migrate from an old architecture to a new architecture. One such approach is so-called xe2x80x9con-line interpretation or emulation.xe2x80x9d In on-line interpretation or emulation, a software emulator module is used to provide an environment which emulates the instruction environment of the old architecture using the instruction set of the new architecture. The emulator or interpreter as it is sometimes referred to thus interprets instructions from an executable version of the application program written in a non-native instruction set and converts those instructions to an executable instruction or series of instructions or routines.
As part of the process, the interpreter tests the instructions to determine the resources needed by the instruction and analyzes the instruction to determine the function of the instruction. From this testing and analysis, the interpreter maps the instruction to a routine that performs the same function only written for instructions executable on the new architecture. The native instruction of routine is executed in the computer system to provide the equivalent function called for in the application program written in the non-native instruction set.
Interpreters are useful to convert application programs between architectures at run time. One of the significant drawbacks of interpreters, however, is that they are exceedingly slow. Thus, performance advantages of the fast or high performance architectures are often lost with using the interpreter to convert instructions from the old architecture to a new architecture.
A second technique commonly used is so-called xe2x80x9con-line binary translation.xe2x80x9d In on-line binary translation, a software program called a translator receives the non-native instructions of the old architecture and for each instruction provides an instruction sequence in the new architecture to accomplish what the original instruction does in the old architecture.
While a on-line binary translator is generally faster than an interpreter, one problem with an on-line translator is that often times non-native statements in the executable image are translated assuming that the statements were instructions when in fact the statements were not instructions but rather data or some other noninstruction information. While this drawback may not cause problems in the execution of the application program since the translator of non-native instructions are never reached. Nevertheless, this extra translation increases the size of the memory file required to store the translated image and reduces the overall performance of the translation. Furthermore, the translation of non-native code minimizes the opportunity to run the translator code through an optimizer and provide a more optimized routine for the translator.
Optimizers are compiler types of routines which generally operate on source code to determine opportunities for reordering and otherwise optimizing the source code to optimized object code. Optimizers have generally limited use with on-line translators because of the aforementioned problems regarding translation of non-native code. In particular, present optimization routines of translated code generally operate on a so-called xe2x80x9cbasic blockxe2x80x9d of instructions. A basic block of instructions can be viewed as a series of instructions which has a single entry point and which ends in a control transfer with a guarantee that none of the instructions between the entry point and the control transfer are themselves control transfers.
Thus, when an optimizer operates on a basic block of instructions, the opportunities for reordering and otherwise optimizing the executable code are limited to those opportunities which occur in the basic block. Thus, unlike the situation in compilers, an optimizer for an on-line binary translator is generally limited to optimization within a basic block.
An application program can be converted into a compound image which includes the original non-native image of the application program as well as selected, translated portions of the application program provided in native image code. Such a converted application program can be provided by a binary image conversion system which includes an on-line system which may be an emulator, interpreter or translator. In response to non-native instructions of an application program, the binary image conversion system provides a native instruction or a native instruction routine. The native instructions or routines are executed. In response to their execution profile data related to the execution characteristics of the native instructions and routines are collected. The image conversion system also includes a background translator system which in accordance with the profile data generated by the on-line emulator system, provides a translated and preferably optimized native image of the non-native application program image.
In general, the translated native image of the application program is executed on the computer system except for those portions of the program which do not have translated images. In those situations the non-native image of the application program is executed by the on-line system here an interpreter. Those portions of the non-native image for which execution characteristics of the instructions cannot be explicitly predicted or determined are not translated.
One problem associated with execution of an application program using native image and non-native image portions of the program is maintaining a stack of return addresses in the non-native image for routines which are executed in the native image without being invasive to the non-native image. That is, in the above arrangement when a computer system executes interpreted code at some point in the execution or subsequent executions, the computer system will be asked to execute translated native code. Once the translated native code is executed, it might not be possible for the computer system to call subsequent translated native code routines of the application program. This could occur if the translated image calls other translated images prior to returning to the non-native image or if the translated image branches to an unknown target, that is a computed branch or switch that is a non-PC relative target.
In each of these circumstances, therefore, it would require that the interpreter be used to interpret execution code. However, since the return address of the original instruction is not stored, it is impossible for the interpreter to return to execution of translated image code. This problem is most manifest in translated images which are optimized over more than a basic block. As mentioned above, a basic block of instructions is a sequence of instructions having a single entry point and a single control transfer with a guarantee of no control transfers occurring between the entry point and the control transfer point of the instruction. In background translator routines it will be possible to optimize translated images over larger regions than just basic blocks. That is, entire routines or possibly even application programs can be optimized. Therefore, it is highly likely that when a translated image of an application program is executed, a call into the native image code in the translator image will result in other calls into the translated image.
It would be unacceptable to permit the translated image to call other routines in the translator image unless a mechanism is provided to allow these other calls to return to the original execution point of the image. Otherwise, in order to return to execution of the program it would be necessary for the interpreter to provide return instructions to the non-native image.